﻿#include<stdio.h>
#include<stdbool.h>
#include <malloc.h>
#include<string.h>
//题目：括号的匹配 https://leetcode.cn/problems/valid-parentheses/
// 都是用栈的方法来解决
//第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false

//第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false

//第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false
//法一
bool isValid(char* s) {
    int len = strlen(s);
    int* stack = malloc(sizeof(int) * len);
    int count = 0;
    for (int i = 0; i < len; i++) {
        if (s[i] == '(') {
            stack[count++] = ')';
        }
        else if (s[i] == '{') {
            stack[count++] = '}';
        }
        else if (s[i] == '[') {
            stack[count++] = ']';
        }
        else if (count == 0 || stack[count - 1] != s[i]) {
            // ⬆情况 2 和情况 3
            return  false;
        }
        else {
            count--;
        }
    }
    // 情况 1
    return count == 0;
}
//法二
char pairs(char a) {//将字符进行简单转换，方便后面比较判断
    if (a == '}') return '{';
    if (a == ']') return '[';
    if (a == ')') return '(';
    return 0;
}

bool isValid(char* s) {
    int n = strlen(s);
    if (n % 2 == 1) {//如果长度为奇数，肯定会存在一个不匹配，提前结束
        return false;
    }
    int stk[5000];
    int top = 0;//初始化变量
    for (int i = 0; i < n; i++) {//遍历字符串每一个元素
        char ch = pairs(s[i]);//简单处理
        if (ch) {//出栈
            if (top == 0 || stk[top - 1] != ch) {//栈顶元素匹配不成功，返回false，不能匹配
                return false;
            }
            top--;//匹配成功，将栈顶元素弹出
        }
        else {//入栈
            stk[top++] = s[i];
        }
    }
    return top == 0;//栈中无任何元素，说明全部匹配成功
}
